package com.datastructure.test.dividelistnode;

public class DivideListNode {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.next=new ListNode(4);
        listNode.next.next=new ListNode(3);
        listNode.next.next.next=new ListNode(2);
        listNode.next.next.next.next=new ListNode(5);
        listNode.next.next.next.next.next=new ListNode(2);
        DivideListNode divideListNode = new DivideListNode();
        ListNode partition = divideListNode.partition(listNode, 3);
        System.out.println(partition);
    }

    public ListNode partition (ListNode head, int x) {
        // 双指针解法
        ListNode leftP = new ListNode(0);
        leftP.next = head;
        //哑结点，输出结果
        ListNode dummyHead = leftP;
        while(leftP.next!=null && leftP.next.val < x){
            leftP = leftP.next;
        }
        //插入点的next（插入点的后结点）
        ListNode nextP = leftP.next;
        //右指针，寻找需要前移的结点
        ListNode rightP = nextP;
        while(rightP!=null && rightP.next!=null){
            //找到需要前移的结点，执行插入操作
            if(rightP.next.val < x){
                leftP.next = rightP.next;
                rightP.next = rightP.next.next;
                leftP.next.next = nextP;
                leftP = leftP.next;
                //该结点不需要前移
            }else{
                //滑动右指针
                rightP = rightP.next;
            }
        }
        return dummyHead.next;
    }
}
class ListNode {
   int val;
   ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}
